The present invention relates to a content addressed memory (CAM), and more specifically to a detecting circuit and a detecting method of an idle word having no data to be retrieved in a CAM having valid cells.
The content addressed memory (CAM) is a semiconductor memory in which by adding a data retrieving device to the semiconductor memory, whether or not data matching the inputted retrieval data exists in the memory is detected, in addition to the normal data read/write operation, and if there is matching data, the address of it is outputted, otherwise the absence of such data is outputted. The typical CAM comprises, as shown in FIG. 1, an address/data circuit (bus) 1, an input-output/control circuit 2, and a plurality of memory blocks 3.
FIG. 2 is a diagram showing the memory block 3 of the conventional CAM. The memory block 3 includes an address decoder 10, a data write driver 11, a data read sense amplifier 12, and a CAM cell array 13, which are seen in the typical memory, and in addition, includes a data retrieve driver 11, word match lines 14, valid cells 15, valid 16, a word match circuit 17, and an address encoder 18. Since the data retrieve driver can also be used as the data write driver, it is denoted by the same symbol 11 in FIG. 2, and has a function of sending retrieval data to the bit line of the cell array when data is retrieved. The valid cells 15 are a memory cell existing for each word address. The valid cell 15 is a memory which holds xe2x80x9cfalsexe2x80x9d (bit xe2x80x9c0xe2x80x9d) if data is not written in its word address, and holds xe2x80x9ctruexe2x80x9d (bit xe2x80x9c1xe2x80x9d) that is written if data is written.
To the word match lines 14, the result of the comparison between the retrieval data and the data in the memory cell for each word address, which is made when data retrieval is performed, is outputted. The word match circuit 17 is connected to the CAM cell array 13 through the word match lines 14. The word match circuit 17 is a circuit which determines and outputs the presence or absence of matched data upon receipt of the valid 16, which is the output of the word match line 14 and the valid cells 15. The address encoder 18 receives the output of the word match circuit 17, assigns specified weight to it, and creates and outputs an address. The assigning of a specified weight means, for instance, increasing the priority of a low address.
Now, the operation of the CAM of FIG. 2 will be described. FIG. 3 is a diagram for explaining the data flow in the CAM. In FIG. 3, at the word address 0 to address 6 of the CAM cell array, the shown seven data are stored. In the valid cells for the word addresses 0, 1, 3, 5, and 6, a bit xe2x80x9c1xe2x80x9d showing the presence of data to be retrieved is stored. Further, the valid cells for the word addresses 2 and 4 have stored therein a bit xe2x80x9c0xe2x80x9d showing the absence of data to be retrieved (data is invalid), in other words, showing that data is not written yet, or data has become invalid after written.
Now, suppose that retrieval data shown by a symbol 20 in FIG. 3 is inputted by the data retrieve driver 11 (FIG. 2). To the word match lines 14, the results of the comparisons made between the retrieval data and the memory cells for the respective word addresses in the data retrieval are outputted. Upon receipt of the valid 16 which is the output of the word match line 14 and the valid cells 15, the word match circuit 17 detects the presence or absence of matched data and provides an output. If there is a match between the retrieval data and the data in the cell, it outputs a bit xe2x80x9c0.xe2x80x9d Inversely, if there is no match between the retrieval data 20 and the data in the cell, it outputs a bit xe2x80x9c1.xe2x80x9d In the example of FIG. 3, data are matching at the word addresses 1, 2, and 6. However, for the address 2, since there is a bit xe2x80x9c0xe2x80x9d in the valid cell, the output of the word match circuit is xe2x80x9c1.xe2x80x9d Accordingly, only the word match outputs for the addresses 1 and 6 are xe2x80x9c0,xe2x80x9d and the remaining addresses are xe2x80x9c1.xe2x80x9d
The address encoder 18 receives the output of the word match circuit 17, and outputs the smallest address. In the example of FIG. 3, it outputs the smaller address 1 of the two matching addresses, addresses 1 and 6. Simultaneously, it outputs xe2x80x9ctruexe2x80x9d as the match output.
There are the following problems with the conventional CAM described using FIGS. 1 to 3.
(1) It is not clear whether or not the CAM has an xe2x80x9cempty addressxe2x80x9d (idle word) in which no data is written.
(2) It is not clear which address of the CAM is an xe2x80x9cempty address.xe2x80x9d
(3) To solve the problems (1) and (2), to know the presence or absence of an xe2x80x9cempty addressxe2x80x9d (idle word), and if there is an xe2x80x9cempty addressxe2x80x9d (idle word), to know that address, it is necessary to provide a new circuit outside the CAM.
The present invention was made to solve the above problems of the CAM. Its object is to enable the knowing of the presence or absence of an xe2x80x9cempty addressxe2x80x9d in the CAM, and knowing of the particular address if there is an xe2x80x9cempty address.xe2x80x9d
It is an object of the present invention to enable the knowing of the presence or absence of an idle word and the word address of the idle word if it is present, without providing a new circuit outside the CAM.
It is an object of the present invention that, in the CAM having valid cells, the data in the valid cells and an address encoder are used to enable an idle word to be detected and outputted.
In accordance with the invention, a detection circuit of an idle word for a content addressed memory having valid cells is provided, which comprises means for supplying the output of a valid cell to an address encoder in response to an idle word detection signal.
In accordance with the invention, a content addressed memory (CAM) is provided, which comprises CAM cells, valid cells, word match lines, a word match circuit, an address encoder, a circuit for detecting an idle word by using the output of valid cells.
In accordance with the invention, a detection method of an idle word for a content addressed memory having valid cells is provided, which comprises a step of writing bit data representing the presence or absence of valid data to a valid cell, and a step of outputting the bit data of a valid cell to an address encoder in response to an idle word detection signal.